The present invention relates generally to automated image processing and sorting, and specifically to automatic location of barcodes on material being sorted.
Postal services and package delivery companies typically handle as many as several million parcels each being used increasingly in order to improve the efficiency and accuracy with which this huge volume of parcels is handled.
The process of sorting and tracking parcels as they proceed through sorting centers requires that each parcel bear two types of information: the destination address of the parcel and a tracking number, which uniquely distinguishes it from other parcels in the system. The information is generally printed on a parcel label, with the destination address in alphanumeric form. The tracking number, and frequently the address, as well, are printed in a machine-readable form, typically as a barcode. While the destination address tells where the parcel is to go, the tracking number assists the postal service or parcel company in managing its shipment operations and enables it to track parcels as they move through the system.
In order to sort and route the parcels automatically, the destination address and tracking number are typically read by a high-resolution imaging system. An image processor must then rapidly locate and read the barcode and the destination address on the parcel. This task is complicated by the fact that parcels vary greatly in size and shape, and may be placed on a conveyor belt for sorting in substantially any orientation. Furthermore, it frequently occurs that barcodes are located close to text and other graphic elements, as well as to tape or other shiny plastic items on the parcel, all of which add substantial xe2x80x9cnoisexe2x80x9d to the barcode search. There is therefore a need for robust, high-speed methods that are capable of finding barcodes in a very large, noisy image within the tight time constraints of a large-volume package sorting system.
An exemplary method for locating barcodes, particularly two-dimensional barcodes, is described by Wang in U.S. Pat. No. 5,304,787, which is incorporated herein by reference. A stored image is processed to identify traversal of barcode start and stop patterns and to correlate these patterns with a common barcode image. The correlated patterns are used to identify a nominally rectangular area bounding the barcode in the image. The corners of the bounding area are used to identify the barcode for subsequent decoding.
Preferred embodiments of the present invention provide improved methods and systems for rapidly locating barcodes and other striped structures in a large and/or noisy image. For this purpose, the image (or a region of interest within the image) is divided up into tiles. Each tile is scanned along one or more parallel lines in order to detect patterns of parallel stripes that could be indicative of the presence of a barcode in the tile. Preferably, each tile is also scanned at a diagonal to the original scan direction, in order to detect patterns of stripes that are parallel or perpendicular to the original scan direction and might otherwise be missed. Tiles that are found to contain a sufficient number of mutually-parallel stripes are tagged as likely locations for a barcode. The angle of the stripes in these tiles provides an estimate of the orientation of the barcode.
Using this method, the entire image can be scanned quickly to identify all of the candidate barcode locations, without the need for an exhaustive search over all pixels and all possible stripe angles. The identification is largely insensitive to the barcode orientation angles and to the presence of noise and clutter in the vicinity of the barcodes. Based on these candidate locations and the associated orientation estimates, a precise orientation angle is determined for each barcode in the image. This angle is used to construct an exact rectangle that bounds the outline of the barcode. The barcode can then be read reliable, as well as serving as a xe2x80x9clandmarkxe2x80x9d for finding other image features of importance.
Embodiments of the present invention are particularly advantageous in the context of automated mail processing. A parcel sorting system that uses automatic barcode identification for recognizing and processing parcel labels is described, for example, in U.S. patent application Ser. No. 09/567,700, which is assigned to the assignee of the present patent application and is incorporated herein by reference. The principles of the present invention will also be found useful, however, in other applications in which barcodes or other striped structures must be identified in digital images, and particularly in large, noisy images.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for locating a barcode in an image, including:
dividing the image into a plurality of tiles;
scanning each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles;
analyzing the pattern of stripes so as to determine an angle of orientation of the barcode; and
responsive to the determined angle, defining bounds of the barcode that are aligned with the pattern of the stripes.
Preferably, scanning each of the tiles includes scanning so as to detect the pattern of stripes substantially irrespective the angle of orientation of the barcode. Most preferably, scanning each of the tiles includes scanning on a first line through the tile in a first scan direction so as to detect the stripes in the tile that are crossed by the first line, and scanning on a second line through the tile in a second scan direction, at a diagonal to the first direction, so as to detect the stripes in the tile that are crossed by the second line.
Preferably, scanning each of the tiles includes detecting the pattern of stripes in a first one of the tiles, and defining the bounds of the barcode includes seeking the bounds of the barcode in at least a second one of the tiles, adjacent to the first one of the tiles.
Additionally or alternatively, the stripes have respective ends, and defining the bounds of the barcode includes locating the ends of the stripes and delimiting a rectangle containing the barcode and having sides defined by the ends of the stripes. Preferably, defining the bounds of the barcode includes finding extreme lines of the barcode corresponding to first and last ones of the stripes of the barcode, and locating the ends of the stripes includes scanning along at least some of the stripes intermediate the first and last stripes in a direction parallel to the extreme lines.
Preferably, the method includes reading the barcode responsive to the bounds.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for finding a pattern of parallel stripes in an image, which includes a plurality of pixels having respective pixel values, the method including:
scanning an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range;
starting from each of at least some of the pixels in the sequence, scanning in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range;
joining the endpoint pixels on each side of the line to define respective edges of a first one of the stripes;
repeating the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes; and
comparing the edges of at least the first and second striped to find the stripe pattern in the image.
Preferably, the method includes scanning the area along a further scan line, in a direction diagonal to the first scan direction, so as to locate third and fourth sequences of the pixels on the further scan line having pixel values within the predetermined range, and repeating the steps of scanning in the second direction, joining the endpoint pixels and comparing the edges with respect to the third and fourth sequences of the pixels and the diagonal direction.
Further preferably, comparing the edges includes determining an orientation of the stripes in the pattern. Most preferably, comparing the edges includes identifying the stripes as belonging to the stripe pattern only if the edges are mutually parallel to within a predetermined limit.
In a preferred embodiment, the pattern includes a barcode.
There is additionally provided, in accordance with a preferred embodiment of the present invention, apparatus for locating a barcode in an image, including an image processor, which is arranged to divide the image into a plurality of tiles, to scan each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles, to analyze the pattern of striped so as to determine an angles of orientation of the barcode, and responsive to the determined angle, to define bounds of the barcode that are aligned with the pattern of the stripes.
In a preferred embodiment, the apparatus includes an image capture device, which is arranged to capture the image of an object on which the barcode appears. Preferably, the image processor is arranged to read the barcode responsive to the bounds so as to extract information contained in the barcode, and the apparatus includes a sorter, which is arranged to sort the object responsive to the information.
There is further provided, in accordance with a preferred embodiment of the present invention, apparatus for finding a pattern of parallel stripes in an image, which includes a plurality of pixels having respective pixels values, the apparatus including an image processor, which is arranged to scan an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, to join the endpoint pixels on each side of the line to define respective edges of a first one of the stripes, and to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel values within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.
There is moreover provided, in accordance with a preferred embodiment of the present invention, a computer software product for locating a barcode in an image, including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to divide the image into a plurality of tiles, to scan each of the tiles so as to detect a pattern of stripes associated with the barcode in at least one of the tiles, to analyze the pattern of stripes so as to determine an angle of orientation of the barcode, and responsive to the determined angle, to define bounds of the barcode that are aligned with the pattern of the stripes.
There is furthermore provided, in accordance with a preferred embodiment of the present invention, a computer software product for finding a pattern of parallel stripes in an image, which includes a plurality of pixels having respective pixel values, the product including a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to scan an area of the image along a selected scan line in a first scan direction so as to locate a first sequence of the pixels on the line having pixel values within a predetermined range, and starting from each of at least some of the pixels in the sequence, to scan in a second scan direction, transverse to the first scan direction, to both sides of the line, so as to reach endpoint pixels defined by the first of the pixels on both sides of the line having pixel values outside the predetermined range, to join the endpoint pixels on each side of the line to define respective edges of a first one of the stripes, and to repeat the steps of scanning the area in the first and second scan directions and of joining the endpoint pixels for at least a second sequence of the pixels on the line having pixel vales within the predetermined range, so as to define the respective edges of at least a second one of the stripes, and to compare the edges of at least the first and second stripes to find the stripe pattern in the image.